Monte Carlo Algorithm
   HOME

TheInfoList



OR:

In
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, a Monte Carlo algorithm is a
randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
whose output may be incorrect with a certain (typically small)
probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for
minimum Feedback arc set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...
. The name refers to the grand
casino A casino is a facility for certain types of gambling. Casinos are often built near or combined with hotels, resorts, restaurants, retail shopping, cruise ships, and other tourist attractions. Some casinos are also known for hosting live entertai ...
in the Principality of Monaco at
Monte Carlo Monte Carlo (; ; french: Monte-Carlo , or colloquially ''Monte-Carl'' ; lij, Munte Carlu ; ) is officially an administrative area of the Principality of Monaco, specifically the ward of Monte Carlo/Spélugues, where the Monte Carlo Casino is ...
, which is well-known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by
Nicholas Metropolis Nicholas Constantine Metropolis (Greek: ; June 11, 1915 – October 17, 1999) was a Greek-American physicist. Metropolis received his BSc (1937) and PhD in physics (1941, with Robert Mulliken) at the University of Chicago. Shortly afterwards, ...
.
Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...
s are a dual of Monte Carlo algorithms that never return an incorrect answer. However, they may make random choices as part of their work. As a result, the time taken might vary between runs, even with the same input. If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability, one running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition.


One-sided vs two-sided error

While the answer returned by a
deterministic algorithm In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far ...
is always expected to be correct, this is not the case for Monte Carlo algorithms. For
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s, these algorithms are generally classified as either false-biased or true-biased. A false-biased Monte Carlo algorithm is always correct when it returns false; a true-biased algorithm is always correct when it returns true. While this describes algorithms with ''one-sided errors'', others might have no bias; these are said to have ''two-sided errors''. The answer they provide (either true or false) will be incorrect, or correct, with some bounded probability. For instance, the
Solovay–Strassen primality test The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 ...
is used to determine whether a given number is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least and true with probability less than . Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a ''-correct false-biased algorithm''.


Amplification

For a Monte Carlo algorithm with one-sided errors, the failure probability can be reduced (and the success probability amplified) by running the algorithm ''k'' times. Consider again the Solovay–Strassen algorithm which is ''-correct false-biased''. One may run this algorithm multiple times returning a false answer if it reaches a false response within ''k'' iterations, and otherwise returning true. Thus, if the number is prime then the answer is always correct, and if the number is composite then the answer is correct with probability at least 1−(1−)''k'' = 1−2''−k''. For Monte Carlo decision algorithms with two-sided error, the failure probability may again be reduced by running the algorithm ''k'' times and returning the
majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of t ...
of the answers.


Complexity classes

The
complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...
BPP BPP may refer to: Education * BPP Holdings, a holding company based in the United Kingdom * BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University * BPP University, a private university based in the ...
describes
decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s that can be solved by polynomial-time Monte Carlo algorithms with a bounded probability of two-sided errors, and the complexity class RP describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one-sided error: if the correct answer is false, the algorithm always says so, but it may answer false incorrectly for some instances where the correct answer is true. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. , but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven. Another complexity class, PP, describes decision problems with a polynomial-time Monte Carlo algorithm that is more accurate than flipping a coin but where the error probability cannot necessarily be bounded away from .


Applications in computational number theory

Well-known Monte Carlo algorithms include the Solovay–Strassen primality test, the Baillie–PSW primality test, the
Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
, and certain fast variants of the
Schreier–Sims algorithm The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation c ...
in
computational group theory In mathematics, computational group theory is the study of group (mathematics), groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracted ...
.


See also

*
Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...
s, algorithms used in physical simulation and
computational statistics Computational statistics, or statistical computing, is the bond between statistics and computer science. It means statistical methods that are enabled by using computational methods. It is the area of computational science (or scientific computi ...
based on taking random samples *
Atlantic City algorithm Atlantic City algorithm is a probabilistic polynomial time algorithm that answers correctly at least 75% of the time (or, in some versions, some other value greater than 50%). The term "Atlantic City" was first introduced in 1982 by J. Finn in an ...
*
Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...


References


Citations


Sources

* * * {{refend Randomized algorithms